// ml:run = $bin < input
#include <iostream>
#include <queue>
#include <cstring>
#include <queue>
#include <vector>
#include <unordered_set>

int const maxn = 200007;
int n, m, start;

bool vis[maxn];
bool can[maxn];
int dis[maxn];
std::vector<std::vector<int>> g;

void add_edge(int x, int y)
{
    g[x].push_back(y);
    g[y].push_back(x);
}

void init()
{
    g.resize(n + 1);
    for (auto & i : g) i.clear();
    memset(dis, 0, sizeof(dis));
    memset(vis, 0, sizeof(vis));
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    int T; std::cin >> T;
    while (T--) {
        std::cin >> n >> m;
        init();
        for (int i = 0; i < m; i++) {
            int x, y; std::cin >> x >> y;
            add_edge(x, y);
        }
        std::cin >> start;

        std::queue<int> q;
        q.push(start);
        vis[start] = true;
        std::unordered_set<int> us;
        for (int i = 1; i <= n; i++)
            if (i != start) us.insert(i);
        while (!q.empty()) {
            int now = q.front(); q.pop();
            for (auto i : us) can[i] = true;
            for (auto i : g[now]) can[i] = false;
            std::unordered_set<int> rm;
            for (auto i : us) {
                if (!can[i] || vis[i]) continue;
                q.push(i);
                dis[i] = dis[now] + 1;
                vis[i] = true;
                rm.insert(i);
            }
            for (auto i : rm) us.erase(i);
        }
        bool first = true;
        for (int i = 1; i <= n; i++) {
            if (i == start) continue;
            int ans = -1;
            if (dis[i]) ans = dis[i];
            if (first) {
                std::cout << ans;
                first = false;
            } else std::cout << " " << ans;
        }
        std::cout << "\n";
    }
}

